package 笔试;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Arrays;

public class 数据结构算法 {
    /**
     * 返回根据arr中元素顺序构成二叉搜索树的树层级
     * @param arr int整型一维数组 无序且无数值重复的数组
     * @return int整型
     */
    public static int tdepth (int[] arr) {
        //写的程序与题意不符，没有按照前中后遍历思想
        if (arr.length == 0){
            return 0;
        }
        if (arr.length == 1){
            return 1;
        }
        if (arr.length == 2){
            return 2;
        }
        if (arr.length == 3){
            return 2;
        }
        if (arr.length == 4){
            return 3;
        }
        Arrays.sort(arr);
        Node node = new Node();
        node.data = arr[0];
        int letcount = 1;
        int rightCount = 1;
        for (int i = 1; i < arr.length; i++) {
            if (i<node.data){
                node.letNode = new Node();
                node.letNode.data = arr[i];
                letcount++;
                node = node.letNode;
            }else {
                node.rightNode = new Node();
                node.rightNode.data = arr[i];
                rightCount++;
                node = node.rightNode;
            }
        }
        return Math.max(letcount, rightCount);
    }
    public static class Node{
        int data;
        Node letNode;
        Node rightNode;
    }

    public static void main(String[] args) {
        System.out.println(tdepth(new int[]{2,3,8}));
    }
}
